1. Field of the Invention
The present invention relates to sharing and updating data across a computer network. More particularly, the present invention relates to sharing and updating data structures within a computer-generated environment shared across said network.
2. Description of the Related Art
Many numerous techniques are known with which to share and update data structures across computer networks. Primarily, such sharing techniques will depend upon the infrastructure of said network. One such infrastructure is referred by those skilled in the art as a distributed system, which may be understood as a collection of user computer terminals whose data distribution is transparent to their respective users, such that the system as a whole appears as one local machine. A common form of distributed system is for instance a client-server architecture, in which data sharing is split between server tasks and client tasks: a client terminal sends requests to a server terminal asking for information or action, whereby the server responds.
Another such infrastructure is known to those skilled to those skilled in the art as a peer-to-peer system, wherein data sharing consists uniquely of client tasks: a client, or peer, sends information or action to another peer or plurality thereof, whereby said information or action is processed by said peers.
Both of the above computer network infrastructures feature advantages and inconveniences according to the type of application and the data or data structures which clients or peers share. Typically, latency is an important factor determining which network infrastructure best suits an application's needs, wherein latency may be understood as the time it takes for a data packet (the shared data or data structure or a portion thereof) to cross a network connection, from sender to receiver. For example, an application for which the frequency of shared data update is not critical but for which the coherence of the application state each terminal shares the data thereof is paramount, may best use the above client-server architecture.
FIG. 1
FIG. 1 shows a computer network wherein two clients share the data of an application by means of a server over a period of time defined by the above latency, according to the known prior art. Two clients A1 and A2 are connected to a server A3 via the Internet A4. In the example, the latency L1 between client Al and server A3 is smaller than the latency L2 between said server A3 and client A2, whereby it takes less time for a data packet to cross the network connection between Al and A3 than it does for said data packet to cross the network between A3 and A2. According to the known prior art, it is known to configure server A3 to counter act the above latency difference such that the exchange of information or actions between clients A1 and A2 is coherent. It should be appreciated here that latency can be two-way (the amount of time it takes for a round-trip signal, or ping, to return to a system) or one-way (the amount of time is takes for a signal to reach one system from another). In this prior art example such as this the latency is usually two-way.
For instance, if client A1 was to perform an action A5, the defining data of which should be shared with client A2 and, conversely, client A2 was to perform an action A6, the defining data which should be shared with client A1 at exactly the same time, said respective data packets would be sent via server A3 configured to delay the confirmation A7 of action A5 at client Al by a factor A8, such that said confirmation A7 includes data defining the action A6 of client A2 performed at the same time as action A5 and similarly, confirmation A9 at client A2 includes data defining action A5 performed at the same time as action A6 at client A2. The state of the application respectively running at A1, A2 is thus coherent at time A10.
Whilst the above configuration is highly desirable for non-time-critical application, such as financial applications the shared data of which should be authenticated by a central server such as server A3 and coherent at all times for users of client terminals such as terminals A1 and A2, it is highly expensive in terms of servers acquisition, administration and maintenance costs, often as not amounting to hundreds of thousands of pounds per server per year. Moreover, more time-sensitive applications such as leisure applications with a highly-dynamic content, e.g. games involving highly-dynamic avatars, are highly penalised by the delaying configuration described thereabove, wherein the delaying factor A8 implemented at server A3 is experienced at client A1 as a phenomenon known to those skilled in the art as “lag”.
For such dynamic applications, the peer-to-peer architecture is preferred because it does not require a server to receive, co-ordinate and redistribute respective application state updates, since each client sends said updates (i.e. shared data or data structures) to every other client to which it is connected. In other words, for a number N of peers, each peer must send one data update to (N-1) peers for each action, such as action A5, wherein N peers sending (N-1) data updates generates a number of data updates increasing like N2.
Whilst the above architecture is preferable for highly-dynamic applications because varying latencies between multiple peers are not compounded by the requirement of co-ordinating messages at a server such as server A3, the latency inherently existing between two peers may result in an incoherent application state. This problem is shown in FIG. 2, wherein two peers B1, B2 run a racing game application and are connected to the Internet A4, by means of which they share respective application state updates. In the example, we assume the racing game application respectively running at peers B1, B2 has a rate of displaying the application state of sixty frames per second, thus generates a frame every seventeen milliseconds or so. The latency L3 between peers B1, B2 is two hundred milliseconds. In the example still, updates B3, B4 correspond to a similar action respectively performed at client B1 and B2, wherein said action B3 is triggered at client B1 a few milliseconds before action B4 is triggered at client B2.
If said actions B3, B4 define an event, the duration of which exceeds the latency L3, the respective application state updates will be coherent at both B1 and B2, whereby B1 has “won”. However, if said event duration is inferior to the latency L3, for instance of ten frames or one hundred and seventy milliseconds shown at B5, then at time B6 client B1 may rightly believe it has “won” whilst a few milliseconds later at time B7, client B2 will also think it has won, because the respective update B3, B4 have not yet been received by the opponent. This result is clearly incoherent.
FIG. 2
Various techniques are known to those skilled in the art to address the problem described in FIG. 2. A first such technique is known as “bucket synchronisation” and is described in FIG. 3. With reference to FIG. 2, peers B1, B2 respectively broadcast application state updates B3, B4 to one another and to a third peer C1 also partaking in said racing game application and broadcasting its own application state update C2 to said peers B1, B2. Bucket synchronisation relies upon the racing game applications respectively running at peer B1, B2 and C1 updating its state every sixtieth of a second for display, wherein a conceptual “bucket” of said application collects local and remote application state updates during each frame.
Thus, in the example, the application running at peer B1 collects the local update B3, remote update B4 of peer B2 and remote update C2 of peer Cl in order to generate the next displayed frame C3, wherein the applications respectively running at peers B2 and C1 perform the same function. Upon generating said frame C3, said conceptual bucket is “emptied” whereby new local and remote updates can be collected to generate the next displayed frame C4 and so on and so forth.
In the eventuality of a missing application state update, it is known for the application to extrapolate said missing update's last received valid data in order to generate said frame C4. For instance, a new action C5 is input at peer B2 and subsequently broadcast and received at peer B1 but is not received by peer C1 until after C1's application generates said frame C4, as shown at C6. The application running at peer C1 thus extrapolates the data of application state update B4, which is the last received input data from peer B2 in order to generate said frame C4. Bucket synchronisation is thus a very fast technique to locally update shared data processed by applications running at peers.
A major problem with said bucket synchronisation technique, however, is that errors arising from said extrapolation may eventually corrupt the application state at all the peers sharing the data and/or data structures thereof. According to the known prior art, the “capacity” of the bucket in buckets synchronisation is either arbitrarily fixed, whereby a next frame such as frame C4 is generated every so often irrespective of the processing capacity of the peer computer terminal, for instance fixed at twenty five frames per second where say peer B1 has adequate processing capacity to sustain an update rate of sixty frames per second. This situation prevents peer-to-peer applications so configured to maximize the update speed they can achieve.
Alternatively, said update rate is not arbitrarily fixed, but this compounds the errors in dead reckoning as described above. Indeed, if said update rate is not fixed and peer B1 can sustain an update rate of sixty frames per second but peer C1 can only sustain an update rate of thirty frames per second, the application running at peer B1 must extrapolate the shared data or data structures update broadcast from said peer C1 every second frame. To address this particular problem, an alternative technique to bucket synchronisation is known to those skilled in the art as “stop-and-wait synchronisation” and is described in FIG. 4.
FIG. 3 and 4
With reference to the above description of FIG. 3, a local frame C3 displaying an updated application state is similarly generated at each peer B1, B2 and C1 upon receiving local and remote application state updates, such as local update B3 and remote updates B4 and C2 at peer B1 and so on and so forth. To the contrary of bucket synchronisation, however, stop-and-wait synchronisation does not extrapolate last known data of missing application state updates when generating the next frame C4 but stipulates that for each frame, every peer waits until every other peer has updated its application state before generating said next frame C4.
Thus, if we again take the example of an action C5 at peer B2 being broadcast in a timely fashion to peer B1 but taking longer than usual to arrive at peer C1, the generating of said next frame C4 at each of said peers B1, B2 and C1 is delayed until peer C1 receives said update C5, as shown at D1. Stop-and-wait synchronisation is thus a very reliable technique to ensure application state updates are coherent at all of the partaking peers B1, B2 and C1 but is as slow for all partaking peers as the highest latency between two of said partaking peers B2, C1. In this respect, it features the same distinct disadvantage as the client/server architecture described in FIG. 1.
What is therefore required is a computer network configured to share and update data and/or data structures, wherein the application state coherency derived from each client updating all other clients it is connected thereto is maintained at each of said clients in a manner as reliable as afforded by the above “stop-and-wait synchronisation” technique, but wherein the rapidity with which each client may update its respective application from said local and remote updates featured by the above bucket synchronisation is maintained.